package com.huffmantree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class HuffmanTree {
    public static void main(String[] args) {
        int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
        Node root = createHuffmanTree(arr);
        preOrder(root);
    }

    /**
     * 创建赫夫曼树
     * @param arr 待排序的序列
     * @return 返回赫夫曼树的根结点
     */
    public static Node createHuffmanTree(int[] arr){
        //将数组装换成ArrayList方便操作
        ArrayList<Node> nodes = new ArrayList();
        for(int val : arr){
            nodes.add(new Node(val));
        }
        //循环创建赫夫曼树过程为在已排序的集合中获取两个val最小的结点合并，再加入到集合中重写排序...
        //直到集合中只剩下一个结点，即根结点
        while(nodes.size() != 1){
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //有两个结点创建子树
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            nodes.add(parent);
            nodes.remove(rightNode);
            nodes.remove(leftNode);
        }
        return nodes.get(0);

    }
    /**
     * 赫夫曼树的前序遍历，传入根节点进行遍历
     */
    public static void preOrder(Node root){
        if(root == null){
            System.out.println("该树为空树，无法进行遍历");
        }else {
            root.preOrder();
        }
    }
}
